This invention relates to computer data structures and algorithms, and more particularly to a data structure for representing a time-varying variable and to algorithms that use the data structure.
As applications for computer software get increasingly complex and sophisticated, so does the need for efficiency in performance of the software. An example of complex software is the xe2x80x9centerprisexe2x80x9d software being used to model the operation of businesses, such as manufacturers or service providers.
An enterprise model typically models time-varying quantities, such as inventory. The enterprise model often further models scheduling type processes, where resources and their availability are represented.
Enterprise software typically permits the user to enter queries about time-varying quantities. Sometimes the query might be a simple xe2x80x9cfunction valuexe2x80x9d type of query, such as, xe2x80x9cHow many on hand at time t?xe2x80x9d. However, a more practical xe2x80x9cfindxe2x80x9d type of query asks for earliest/latest or maximum/minimum information. For example, a query seeking both xe2x80x9cearliestxe2x80x9d time and xe2x80x9cminimumxe2x80x9d amount information might ask, xe2x80x9cFind the earliest time greater than t at which we will have a minimum of n units of material on hand?xe2x80x9d. In this example, t is the earliest time at which a task might be scheduled (due to other constraints) and n is the number of units of material that the task will consume.
One approach to solving queries involving time-varying variables is to represent values of the variable with a xe2x80x9cbinary treexe2x80x9d. A binary tree is a type of data structure known in the art of algorithms, which arranges data hierarchically. The tree may be queried to obtain data about the variable.
One commercially available enterprise model, manufactured by Optimax Corporation under the trademark OPTIFLEX, used a binary tree to represent a time varying function. At each node, certain values relative to the xe2x80x9csubtreexe2x80x9d of that node were stored.
One aspect of the invention is a method of storing values of a time-varying variable. The variable is represented as a time-varying function having time values and function values. The time-varying function is then represented as a binary tree, each node of the tree associated with a change in value of the function. The tree is balanced such that each child node having a value less than that of its parent node is to the left of the parent node and each child node having a time value greater than that of its parent node is to the right of the parent node. The stored values at each node are a time value, a delta value, a maximum subtree value, and a minimum subtree value. The latter two xe2x80x9csubtree valuesxe2x80x9d are referred to as such because they represent a relative contribution from the subtree beginning with that node. The tree has an associated bounding box function callable from any node, which is operable to use that node""s subtree values to calculate one or more bounds of values of the function within the subtree. These bounds may be time bounds or quantity bounds.
An advantage of the invention is that the tree provides solutions to xe2x80x9cearliestxe2x80x9d and xe2x80x9clatestxe2x80x9d type queries. Morever, these queries may specify time limits, such as xe2x80x9cearliest after time txe2x80x9d or xe2x80x9clatest before time txe2x80x9d.